/* 
permmult.c 
mnozenie permutacji w postaci cyklowej
D. Knuth, TAOCP, 1.3.3, algorytm A
*/

#include <string.h>
#define N strlen(perm) // dlugosc napisu dla iloczynu cyklow
#define N_MAX 256 // maksymalna dlugosc napisu

char perm[] = "(acfg)(bcd)(aed)(fade)(bgfae)"; // iloczyn cyklow
int mark[N_MAX]; // tablica oznaczen
int s = 0; // indeks pozycji elementu na wyjsciu
char out[N_MAX]; // wyjscie

void marked(char , int); // oznaczanie liter w tablicy mark[]
void replace_right_brackets(); // przypisanie symboli wejsciowych do prawych nawiasow
void output(char ); // wyprowadzenie znaku na wyjscie
void czy_stop();

int main()
{
  int i, j, k, l, cnt;
  char START; // zmienna pomocnicza
  char CURRENT; // zmienna pomocnicza
 A1: // pierwszy przebieg
  printf("%s\n", perm);
  marked('(', 1); // oznaczenie lewych nawiasow
  replace_right_brackets(); // zastapienie prawych przez symbol wejsciowy
 A2: // rozpoczecie
  czy_stop(); // warunek zakonczenia
  i = 0;
  while (mark[i] != 0) // wyznaczenie elementu nieoznaczonego
    i = i+1;
  START = perm[i];
  output('('); // wyprowadzenie nawiasu
  output(START); // wyprowadzenie elementu
  mark[i] = 1; // oznaczenie elementu
  k = i+1; // nastepny element
 A3: // ustawienie current
  CURRENT = perm[k];
 A4: // przejscie
  for (j = k+1; j < N; j++)
    if (perm[j] == CURRENT) {
      mark[j] = 1;
      k = j+1;
      goto A3;
    } 
 A5: // czy CURRENT = START?
  if (CURRENT != START) {
    output(CURRENT);
    k = 0;
    goto A4;
  }
 A6: // zakonczenie
  output(')');
  goto A2;
}

// implementacje funkcji

void marked(char a, int m)
{
  int i;
  for (i = 0; i < N; i++)
  if (perm[i] == a)
    mark[i] = m;
}

void replace_right_brackets()
{
  int i, j;
  for (i = 0; i < N; i++)
    if(mark[i] == 1)
      for(j = i; j < N; j++)
	if (perm[j] == ')') {
	  perm[j] = perm[i+1];
	  break;
	}
}

void output(char a)
{
  out[s++] = a;
}

void czy_stop()
{
  int i;
  int cnt = 0;
  for (i = 0; i < N; i++) // zliczanie pozycji oznaczonych 1
    if (mark[i] == 1) 
      cnt++;
  if (cnt >= N-5) { // warunek zakonczenia
    printf("%s\n", out);
    exit(0);
  }
}
